package com.xiaoh.leetcode.easy;

/**
 * @author xiaoh
 * @ClassName RunningSum_1480
 * @Description TODO
 * @Date 2020/8/19 15:00
 * @Version 1.0
 */
public class RunningSum_1480 {

    public static int[] runningSum(int[] nums) {
        int[] result = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            int sum = 0;
            for (int j = 0; j <= i; j++) {
                sum += nums[j];
            }
           result[i] = sum;
        }

        return result;
    }

    public static void main(String[] args) {
        int[] result = runningSum(new int[]{1,2,3,4,5});
        for (int i = 0; i < result.length; i++) {
            System.out.println(result[i]);
        }
    }

    /**
     * 功能描述 暴力解法时间复杂度O(n^2)
     *
     * @param [nums]
     * @return int[]
     */
    public int[] runningSum1(int[] nums) {
        int temp[] = new int[nums.length];
        temp[0] = nums[0];
        for(int i = 1;i < nums.length; i++){
            int ans = nums[i];
            for(int j = i -1;j >= 0;j--){
                ans += nums[j];
            }
            temp[i] = ans;
        }
        return temp;
    }

    /**
     * 功能描述 动态规划 时间复杂度O(n),动态求和公式：temp[i] = temp[i-1] + nums[i];
     *
     * @param [nums]
     * @return int[]
     */
    public int[] runningSum2(int[] nums) {
        int temp[] = new int[nums.length];
        temp[0] = nums[0];
        for(int i = 1;i < nums.length ;i++){
            temp[i] = temp[i-1] + nums[i];
        }
        return temp;
    }

}
